package com.example.algorithm.sort;

// 学习顺序：第四

// 对比学习：这个例子可以和MergeSortedLinkedListSolution类中的那个例子，对比一起学习来看。两者有共通之处。

// 把待排序队列分为n个有序的子队列，再合并他们，其实也是分治法思想的一种使用。复杂度：n*logn
// 算法分析：归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。
// 个人备注：分开我理解，但是，两个有序数组怎么合并为一个大的有序数组呢？这个算法是不是要参考另外一个题目：合并两个已经排序的链表???

// 其实，归并排序的代码是相对来说比较简单的。
public class MergeSort {
    public static void main(String[] args) {
        int[] array = {5, 3, 9, 8, 4, 2, 6, 1, 7};

        System.out.println("排序前的数组：");
        printArray(array);

        mergeSort(array);

        System.out.println("\n排序后的数组：");
        printArray(array);
    }

    // 归并排序方法
    public static void mergeSort(int[] array) {
        int n = array.length;
        if (n < 2) { // 小于2就没法分了。本递归层级的mergeSort方法直接返回。接着会走上一层级的mergeSort方法里面的merge逻辑，merge方法里面有具体的比较大小的逻辑。
            return;
        }
        int mid = n / 2; // n为9，奇数，那么就是商4，余数1，mid是取4。
        int[] leftArray = new int[mid]; // 长为4的空数组
        int[] rightArray = new int[n - mid]; // 长为5的空数组。

        // 分割原数组为左右两个子数组。它这种分治法，是按照长度来分的。
        for (int i = 0; i < mid; i++) {
            leftArray[i] = array[i];
        }
        for (int i = mid; i < n; i++) {
            rightArray[i - mid] = array[i];
        }

        // 递归地对左右两个子数组进行排序
        mergeSort(leftArray);
        mergeSort(rightArray);

        // 合并左右两个有序子数组。这个步骤也是mergeSort方法的一部分，它也会被递归调用的。
        // merge()方法中的第三个参数array，它就是原始array,传进去就是要在array的基础上直接改的。
        merge(leftArray, rightArray, array);
    }

    // 合并两个有序数组方法
    // 总之，这段代码实现了合并两个已排序数组的功能，将两个数组按照顺序合并成一个新的有序数组。
    public static void merge(int[] leftArray, int[] rightArray, int[] array) {
        int leftLength = leftArray.length;
        int rightLength = rightArray.length;
        int i = 0, j = 0, k = 0; // 给i、j、k做初始化。这个初始化，都是从0开始的。左右数组，从0个位置开始比较。而原始array，也从第0个位置开始覆盖。

        // 合并两个有序数组
        // 这个while，i，j都是0开始，都不断递增，上限分别是左右数组长度。达到上限就停止了。
        // 这个while什么时候结束呢？直到左数组或者右数组有一边被率先执行誊写完。但是，另一个如果还没有誊写完那怎么办呢？借助下面的两个while来补上。
        while (i < leftLength && j < rightLength) {
            if (leftArray[i] <= rightArray[j]) { // 实质性的可见的排序逻辑，就在这么关键一句。
                // if和else里面的代码，都是分别将左数组和右数组当前位置的元素放入合并后的数组中，并且同时将相应的索引 i 或 j 向后移动一位，以便比较下一个位置的元素。
                array[k++] = leftArray[i++];
            } else {
                array[k++] = rightArray[j++];
            }
        }
        // 循环结束后，可能存在其中一个数组还有剩余元素未被合并，此时会执行下面的两个 while 循环将剩余的元素放入合并后的数组中。
        // 因为不知道是左数组没有誊写完还是右数组没有誊写完，所以，两个都加上了while。
        while (i < leftLength) {
            array[k++] = leftArray[i++];
        }
        while (j < rightLength) {
            array[k++] = rightArray[j++];
        }
    }

    // 打印数组方法
    public static void printArray(int[] array) {
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

